Discrete Fourier transform (DFT) or Fast Fourier transform (FFT) are often implemented in hardware by factoring large sample series processing into a series of processing stages. In each stage shorter length sample series are processed using corresponding sized FFT modules, also referred to as “butterflies”, “butterfly computations”, or “butterfly operations” to compute the DFT or FFT in a number of stages. The length of the shorter length sample series of each stage of the decomposition is referred to as radix. A radix-x butterfly receives x input samples and produces the same number of x output samples, where each output sample is the weighted sum of the x input samples.
Implementing a DFT or FFT in a mixed and non-mixed radix configuration, both in decimation in time (DIT) and decimation in frequency (DIF) schemes, usually includes a so-called “reordering stage” or “reorder stage”. In DIF, the reorder stage is carried out after the radix processing (butterflies) stages and returns the DFT results in a desired order. In DIT, the reorder stage is carried out as a first stage. In both DIT and DIF, the reorder stage requires complex addressing and out of order memory access.